home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / programm.ing / gfa / gfaexprt.lzh / GFAXPERT.LIB / SORTINT.LST < prev    next >
Encoding:
File List  |  1986-10-19  |  2.3 KB  |  118 lines
  1. ' *******************
  2. ' *** SORTINT.LST ***
  3. ' *******************
  4. '
  5. DEFWRD "a-z"
  6. '
  7. > PROCEDURE quick.sort.int(VAR proc%())
  8.   ' *** sort integer array by recursive Quick Sort
  9.   LOCAL last,dummy%
  10.   last=DIM?(proc%())-1
  11.   @quick.int(1,last)
  12. RETURN
  13. ' ***
  14. > PROCEDURE quick.int(l,r)
  15.   LOCAL ll,rr,i,x,j
  16.   ll=l
  17.   rr=r
  18.   dummy%=proc%(DIV(ADD(l,r),2))
  19.   REPEAT
  20.     WHILE proc%(l)<dummy%
  21.       INC l
  22.     WEND
  23.     WHILE proc%(r)>dummy%
  24.       DEC r
  25.     WEND
  26.     IF l<=r
  27.       SWAP proc%(l),proc%(r)
  28.       INC l
  29.       DEC r
  30.     ENDIF
  31.   UNTIL l>r
  32.   IF ll<r
  33.     @quick.int(ll,r)
  34.   ENDIF
  35.   IF l<rr
  36.     @quick.int(l,rr)
  37.   ENDIF
  38. RETURN
  39. ' **********
  40. '
  41. > PROCEDURE shell.sort.int(VAR proc%())
  42.   ' *** sort integer array by Shell Sort
  43.   LOCAL inc,last,j,k,inserted!,x%,current,previous
  44.   last=DIM?(proc%())-1
  45.   LET inc=last
  46.   WHILE inc>1
  47.     DIV inc,2
  48.     FOR j=1 TO inc
  49.       k=ADD(j,inc)
  50.       WHILE k<=last
  51.         inserted!=FALSE
  52.         x%=proc%(k)
  53.         current=k
  54.         previous=SUB(current,inc)
  55.         WHILE previous>=j AND NOT inserted!
  56.           IF x%<proc%(previous)
  57.             proc%(current)=proc%(previous)
  58.             current=previous
  59.             SUB previous,inc
  60.           ELSE
  61.             inserted!=TRUE
  62.           ENDIF
  63.         WEND
  64.         proc%(current)=x%
  65.         ADD k,inc
  66.       WEND
  67.     NEXT j
  68.   WEND
  69. RETURN
  70. ' **********
  71. '
  72. > PROCEDURE bin.search.int(element%,VAR proc%(),index)
  73.   ' *** find element% in sorted integer array (binary search)
  74.   ' *** global :   FOUND!
  75.   LOCAL first,last,middle
  76.   first=1
  77.   last=DIM?(proc%())-1
  78.   WHILE first<last
  79.     middle=DIV(ADD(first,last),2)
  80.     IF element%>proc%(middle)
  81.       first=ADD(middle,1)
  82.     ELSE
  83.       last=middle
  84.     ENDIF
  85.   WEND
  86.   found!=(proc%(first)=element%)
  87.   IF found!
  88.     index=first
  89.   ELSE
  90.     index=0
  91.   ENDIF
  92. RETURN
  93. ' **********
  94. '
  95. > PROCEDURE bin.search.word(element,VAR proc(),index)
  96.   ' *** find element in sorted word array (binary search)
  97.   ' *** global :   FOUND!
  98.   LOCAL first,last,middle
  99.   first=1
  100.   last=DIM?(proc())-1
  101.   WHILE first<last
  102.     middle=DIV(ADD(first,last),2)
  103.     IF element>proc(middle)
  104.       first=ADD(middle,1)
  105.     ELSE
  106.       last=middle
  107.     ENDIF
  108.   WEND
  109.   found!=(proc(first)=element)
  110.   IF found!
  111.     index=first
  112.   ELSE
  113.     index=0
  114.   ENDIF
  115. RETURN
  116. ' **********
  117. '
  118.